home *** CD-ROM | disk | FTP | other *** search
/ AOL File Library: 2,801 to 2,900 / aol-file-protocol-4400-2801-to-2900.zip / AOLDLs / C++ Files Library / Graphic Gems I, II & III (C_C++) / Graphics Gems C Code.sea / GemsIII / accurate_scan / tri.c < prev   
C/C++ Source or Header  |  1992-06-16  |  6KB  |  237 lines
  1. #include <stdio.h>
  2. #include <math.h>
  3.  
  4. extern void draw_point(int x, int y);
  5.  
  6. #include "fixpoint.h"
  7.  
  8. #define SWAP(_a_, _b_, _c_) { _c_ = _a_; _a_ = _b_; _b_ = _c_; }
  9. #define min(_a_, _b_) ((_a_ < _b_) ? _a_ : _b_)
  10. #define max(_a_, _b_) ((_a_ > _b_) ? _a_ : _b_)
  11.  
  12. struct edge {
  13.   int ymin, ymax, xi, si;
  14.   int r, inc, dec;
  15. };
  16.  
  17. /* floor(x/y). Assumes y>0. */
  18. int floor_div(int x, int y)
  19. {
  20.   if (x >= 0) return(x/y);
  21.   else return((x/y) + (((x % y) == 0) ? 0 : -1));
  22. }
  23.  
  24. /*
  25.  *  Draws pixels in the half-open interval (x1, x2].
  26.  */
  27. void draw_span(int x1, int x2, int y)
  28. {
  29.   int x;
  30.   for (x=x1+1; x<=x2; x++) draw_point(x, y);
  31. }
  32.  
  33. /*
  34.  *  Initializes the Bresenham-like scan conversion for a single edge,
  35.  *  setting values in the structure containing the increment variables.
  36.  */
  37. struct edge *EdgeSetup(struct edge *e, int x0, int y0, int x1, int y1)
  38. {
  39.   int sf, dx = x1-x0, dy = y1-y0;
  40.  
  41.   e->ymin = y0;
  42.   e->ymax = y1;
  43.   
  44.   if (dy != 0) {
  45.      e->si = floor_div(dx, dy);
  46.      e->xi = x0 + e->si;
  47.      sf = dx - e->si * dy;
  48.      e->r = 2*sf - dy;
  49.      e->inc = sf;
  50.      e->dec = sf - dy;
  51.   }
  52.   return(e);
  53. }
  54.  
  55.  
  56. /*
  57.  *  Returns the intersection of edge e with the next scanline.
  58.  */
  59. int EdgeScan(struct edge *e)
  60. {
  61.   int x = e->xi;
  62.  
  63.   if (e->r >= 0) {
  64.      e->xi += e->si + 1;
  65.      e->r += e->dec;
  66.   }
  67.   else {
  68.      e->xi += e->si;
  69.      e->r += e->inc;
  70.   }
  71.   return x;
  72. }
  73.  
  74. /*
  75.  *  Scan-converts a triangle with integer endpoints.  Assumes the
  76.  *  triangle's vertices are ordered so that y0 <= y1 <= y2. 
  77.  */
  78. void sorted_triangle(int x0, int y0, int x1, int y1, int x2, int y2)
  79. {
  80.   int det, yi, xmin, xmax;
  81.   struct edge left, right;
  82.  
  83.   /* Compute handedness of triangle (points left or right) */
  84.   /* (see Pavlidis '82, [Computer Science Press], Ch 14) */
  85.   det = (y1-y0)*(x2-x0) - (x1-x0)*(y2-y0);
  86.  
  87.   /* Setup first pair of edges */
  88.   if (det < 0)
  89.      { EdgeSetup(&left, x0, y0, x2, y2);
  90.         EdgeSetup(&right, x0, y0, x1, y1); }
  91.   else
  92.      { EdgeSetup(&left, x0, y0, x1, y1);
  93.         EdgeSetup(&right, x0, y0, x2, y2); }
  94.  
  95.   /* Scan first pair of edges. */
  96.   for (yi = left.ymin + 1; yi <= min(left.ymax, right.ymax); yi++) {
  97.      xmin = EdgeScan(&left);
  98.      xmax = EdgeScan(&right);
  99.      draw_span(xmin, xmax, yi);
  100.   }
  101.  
  102.   /* Setup third edge */
  103.   if (det >= 0) EdgeSetup(&left, x1, y1, x2, y2);
  104.   else          EdgeSetup(&right, x1, y1, x2, y2);
  105.  
  106.   /* Scan remainder of triangle. */
  107.   for (yi = max(left.ymin, right.ymin) + 1; yi <= left.ymax; yi++) {
  108.      xmin = EdgeScan(&left);
  109.      xmax = EdgeScan(&right);
  110.      draw_span(xmin, xmax, yi);
  111.   }
  112. }
  113.  
  114.  
  115. /* 
  116.  *  Scan-converts a triangle with integer endpoints.
  117.  *  Sorts the vertices, then calls a routine to do the scan conversion.
  118.  */
  119. void triangle(int x0, int y0, int x1, int y1, int x2, int y2)
  120. {
  121.   int tmp;
  122.   if (y0>y1) { SWAP(y0,y1,tmp); SWAP(x0,x1,tmp); }
  123.   if (y0>y2) { SWAP(y0,y2,tmp); SWAP(x0,x2,tmp); }
  124.   if (y1>y2) { SWAP(y1,y2,tmp); SWAP(x1,x2,tmp); }
  125.   
  126.   sorted_triangle(x0, y0, x1, y1, x2, y2);
  127. }
  128.  
  129. /*     The scan-conversion routines for coordinates at subpixel resolution.
  130.  *
  131.  *  SubEdgeSetup initializes the Bresenham-like scan conversion for a
  132.  *  single edge (analogous to EdgeSetup).
  133.  *
  134.  *  Double lenght fixpoint is used to compute alpha below. Alpha
  135.  *  is then truncated (this corresponds to quantizing to a 
  136.  *  particular subpixel while computing the x-intersection of the edge
  137.  *  with the scanline). It will not produces artifacts except for
  138.  *  degenerate databases, in which adjacent polygons don't necessarily
  139.  *  have coincident vertices (see Lathrop, Kirk, Voorhies, IEEE CG&A 10(5),
  140.  *  1990 for a discussion).
  141.  *
  142.  */
  143. struct edge *
  144. SubEdgeSetup(struct edge *e,
  145.                  fixpoint x0, fixpoint y0, fixpoint x1, fixpoint y1)
  146. {
  147.  
  148.   fixpoint ymin, ymax, alpha, beta, sf, xi, si;
  149.   fixpoint dx = x1-x0, dy = y1-y0;
  150.  
  151.   ymin = fp_floor(y0);
  152.   ymax = fp_floor(y1);
  153.  
  154.   if ((dy != 0) && (ymin != ymax)) {
  155.  
  156.      /* Alpha is related to x-intercept with scanline ymin  */
  157.      alpha = fp_trunc(fp_dbladd(fp_dblmultiply(fp_fraction(x0), dy),
  158.                                          fp_dblmultiply(dx, ymin - y0 + fp_fix(1.0))));
  159.      beta = fp_floor_div(alpha, dy);
  160.      xi = fp_floor(x0) + beta;
  161.  
  162.      /* prevent overflow for v. small dy ('si' is only used if dy>=1) */
  163.      if (dy >= fp_fix(1.0)) {
  164.         si = fp_floor_div(dx, dy);
  165.         sf = dx - fp_multiply(si, dy); 
  166.  
  167.         /* (alpha - beta*dy) = fractional part of the x-intercept. */
  168.         e->r = alpha - fp_multiply(beta, dy) + sf - dy; 
  169.         e->si = fp_integer(si);
  170.         e->inc = sf;
  171.         e->dec = sf - dy;
  172.      }
  173.      e->xi = fp_integer(xi);
  174.   }
  175.   e->ymin = fp_integer(ymin);
  176.   e->ymax = fp_integer(ymax);
  177.  
  178.   return(e);
  179. }
  180.  
  181.  
  182. /*  Like integer version, but uses SubEdgeSetup */
  183. void subpixel_sorted_triangle(fixpoint x0, fixpoint y0,
  184.                             fixpoint x1, fixpoint y1,
  185.                             fixpoint x2, fixpoint y2)
  186. {
  187.   struct edge left, right;
  188.   int yi, xmin, xmax;
  189.  
  190.   /* compute determinant using full precision (64 bits) */
  191.   dblfixpoint a = fp_dblmultiply(y1-y0,x2-x0);
  192.   dblfixpoint b = fp_dblmultiply(x1-x0,y2-y0);
  193.   int clockwise = fp_dbllessthan(a, b);
  194.  
  195.   /* Setup first pair of edges */
  196.   if (clockwise) {
  197.      SubEdgeSetup(&left, x0, y0, x2, y2);
  198.      SubEdgeSetup(&right, x0, y0, x1, y1);
  199.   } else {
  200.      SubEdgeSetup(&left, x0, y0, x1, y1);
  201.      SubEdgeSetup(&right, x0, y0, x2, y2);
  202.   }
  203.   
  204.   /* Scan first pair of edges. */
  205.   for (yi = left.ymin + 1; yi <= min(left.ymax, right.ymax); yi++) {
  206.      xmin = EdgeScan(&left);
  207.      xmax = EdgeScan(&right);
  208.      draw_span(xmin, xmax, yi);
  209.   }
  210.  
  211.   /* Setup third edge */
  212.   if (!clockwise) SubEdgeSetup(&left, x1, y1, x2, y2);
  213.   else            SubEdgeSetup(&right, x1, y1, x2, y2);
  214.  
  215.   /* Scan remainder of triangle. */
  216.   for (yi = max(left.ymin, right.ymin) + 1; yi <= left.ymax; yi++) {
  217.      xmin = EdgeScan(&left);
  218.      xmax = EdgeScan(&right);
  219.      draw_span(xmin, xmax, yi);
  220.   }
  221. }
  222.  
  223. /* Like integer version. */
  224. void subpixel_triangle(fixpoint x0, fixpoint y0,
  225.                               fixpoint x1, fixpoint y1,
  226.                               fixpoint x2, fixpoint y2)
  227. {
  228.   fixpoint tmp;
  229.   if (y0>y1) { SWAP(y0,y1,tmp); SWAP(x0,x1,tmp); }
  230.   if (y0>y2) { SWAP(y0,y2,tmp); SWAP(x0,x2,tmp); }
  231.   if (y1>y2) { SWAP(y1,y2,tmp); SWAP(x1,x2,tmp); }
  232.   
  233.   subpixel_sorted_triangle(x0, y0, x1, y1, x2, y2);
  234. }
  235.  
  236.  
  237.